# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName : insert_sort.py
# @Time     : 2024/1/28 22:51
# @Author   : Robot-Zsj
"""
description:

直接插入排序法不但要比较大小，还要移动元素，这也是导致时间复杂度较高的原因。

nums：待排序数组名，为list类型
key：表示当前正在向子集合插入的元素值。因为随着前面元素的向后移动，该元素位置会被覆盖，所以需要提前保存该元素的值
"""


def insert_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]  # 保留当前元素的值
        j = i - 1
        # 当 j>=0, 且nums[i]<nums[j], nums[j+1] = nums[j]
        # 这时候nums[i]的位置就被nums[j]给占用了
        while j >= 0 and key < nums[j]:
            nums[j + 1] = nums[j]
            j -= 1
        # 当上面的条件不满足是，将最开始位置的key放置在当前j的后面
        nums[j + 1] = key
    return nums


print(insert_sort([50, 36, 66, 76, 95, 12, 25]))
